from typing import List


class Solution:
    # Using Kadane's algorithm: O(n)
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        
        curr_max = 0
        global_max = nums[0]

        for i in range(n):
            curr_max = max(nums[i], curr_max+nums[i])
            global_max = max(global_max, curr_max)
        
        return global_max
